﻿#include "SeqList.h"

// 顺序表工具函数
// 空间检查/扩容
void CheckCapacity(SeqList* ps) 
{
	if (ps->size + 1 == ps->capacity)
	{
		ps->capacity *= 2;
		ps->array = (DataType*)realloc(ps->array, sizeof(DataType) * ps->capacity);
		if (ps->array == NULL)
		{
			printf("扩容失败\n");
			exit(-1);
		}
	}
}

// 顺序表-基本操作函数
// 顺序表初始化
void SeqListInit(SeqList* ps, size_t capacity) 
{
	assert(ps);
	assert(capacity > 0);
	ps->capacity = capacity;
	ps->size = 0;
	ps->array = (DataType*)malloc(sizeof(DataType) * ps->capacity);
	if (ps->array == NULL)
	{
		printf("初始化失败\n");
		exit(-1);
	}
}
// 顺序表尾部插入
void SeqListPushBack(SeqList* ps, DataType elem) 
{
	assert(ps);
	CheckCapacity(ps);
	ps->array[ps->size] = elem;
	ps->size++;
}
// 顺序表尾部删除
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}
// 顺序表头部插入
void SeqListPushFront(SeqList* ps, DataType elem)
{
	assert(ps);
	CheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->array[i] = ps->array[i - 1];
	}
	ps->array[0] = elem;
	ps->size++;
}
// 顺序表头部删除
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size - 1; i++) 
	{
		ps->array[i] = ps->array[i + 1];
	}
	ps->size--;
}
// 顺序表查找指定元素下标
int SeqListFind(SeqList* ps, DataType elem)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++) 
	{
		if (ps->array[i] == elem) 
		{
			return i;
		}
	}
	return -1;
}
// 顺序表在指定下标插入元素
void SeqListInsert(SeqList* ps, size_t pos, DataType elem)
{
	assert(ps);
	assert(pos <= ps->size);
	CheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->array[i] = ps->array[i - 1];
	}
	ps->array[pos] = elem;
	ps->size++;
}
// 顺序表删除指定下标元素
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	assert(pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++) {
		ps->array[i] = ps->array[i + 1];
	}
	ps->size--;
}
// 顺序表销毁
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->array);
	ps->array = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
// 顺序表遍历
void SeqListTraverse(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++) {
		printf("%d ", ps->array[i]);
	}
	printf("\n");
}